// hard

// 给定一个未排序的整数数组nums
// 要求找出其中没有出现的最小的正整数，要求实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案

// 思路：哈希表，原地哈希
// 如果使用普通的哈希表，遍历一遍数组，将对应整数存入到哈希表中，再从1开始，依次判断对应正数是否在哈希表中即可，这种做法的空间复杂度为O(n)

// 我们可以将当前数组视为哈希表，一个长度为n的数组，对应存储的元素值应该为[1, n+1]之间，其中还包括一个缺失的元素
// 1. 我们可以遍历一遍数组，将当前元素放到其对应位置上
// 2. 再次遍历一遍数组，遇到第一个元素值不等于下标+1的元素，就是答案要求的缺失的第一个正数
// 3. 如果遍历完没有在数组中找到缺失的第一个正数，则缺失的第一个正数是n+1
// 4. 最后返回我们找到的缺失的第一个正数

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
    let size = nums.length

    for (let i = 0; i < size; i++) {
        while (nums[i] >= 1 && nums[i] <= size && nums[i] !== nums[nums[i] - 1]) {
            let index1 = i;
            let index2 = nums[i] - 1;
            [nums[index1], nums[index2]] = [nums[index2], nums[index1]]
        }
    }
    for (let i = 0; i < size; i++) {
        if (nums[i] !== i + 1) {
            return i + 1
        }
    }
    return size + 1
};

let nums = [3,4,9,1, -1,1,2]
console.log(firstMissingPositive(nums))